package com.mlh.doublepointer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/6/19 17:00
 * @DESCRIPTION
 */
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
// 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
// 输出：6
// 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
public class 接雨水 {
    //方法1：暴力破解（双指针）
    //遍历数组，遍历到一个元素就找他左右两侧最高的柱子，来计算盛水的体积

    //方法二：双指针优化
    //为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。
    // 我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），
    // 右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。
    //当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
    // 即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);（自己高度最高时设置为自己的高度）
    // 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
    //有了maxLeft和maxRight数组，很方便计算出盛水量

    //方法三：单调栈
    //老实说这里用单调栈不是很好理解，所以这里不选择用单调栈

    //使用方法二来完成
    public int method1(int[] height) {
        int len=height.length;
        int[]maxLeft=new int[len];
        int[]maxRight=new int[len];
        int max=0;
        int res=0;
        for (int i = 0; i < len; i++) {
            if(max>height[i]){
                maxLeft[i]= max;
            }else{
                maxLeft[i]= height[i];
                max=height[i];
            }
        }
        max=0;
        for (int i = len-1; i >=0 ; i--) {
            if(max>height[i]){
                maxRight[i]= max;
            }else{
                maxRight[i]= height[i];
                max=height[i];
            }
        }
        //这里可以优化一下，和上面生成maxLeft数组合并在一起，少一遍循环
        for (int i = 0; i < len; i++) {
            res+=Math.min(maxLeft[i],maxRight[i])-height[i];
        }
        return res;
    }

    public int practice(int[] height) {
        //初始化
        int[]maxLeft=new int[height.length];
        int[]maxRight=new int[height.length];
        maxLeft[0]=height[0];
        maxRight[height.length-1]=height[height.length-1];
        int res=0;
        for (int i = 1; i < height.length-1; i++) {
            maxLeft[i]=Math.max(height[i],maxLeft[i-1]);
        }
        for (int i = height.length-2; i >0 ; i--) {
            maxRight[i]=Math.max(height[i],maxRight[i+1]);
        }
        for (int i = 1; i < height.length-1; i++) {
            res+=Math.min(maxLeft[i],maxRight[i])-height[i];
        }
        return res;
    }

    public int practice2(int[] height){
        int len=height.length;
        int[] maxLeft=new int[len],maxRight=new int[len];
        maxLeft[0]=height[0];
        maxRight[len-1]=height[len-1];
        for (int i = 1; i < len; i++) {
            maxLeft[i]=Math.max(maxLeft[i-1],height[i]);
        }
        for (int i = len-2; i >=0 ; i--) {
            maxRight[i]=Math.max(maxRight[i+1],height[i]);
        }
        int res=0;
        for (int i = 0; i < len; i++) {
            res+=Math.min(maxLeft[i],maxRight[i])-height[i];
        }
        return res;
    }
}
